public class Sort {
    /**
     * 直接插入排序
     * @param array
     *      1.定义i j tmp 如果tmp < array[i],则将array[j]->array[j+1],大于则继续移动
     *      2.j<0结束,将tmp放入j+1下标,修改i继续
     *      3.直到i<array.length结束
     *      时间复杂度:O(N^2)
     *      空间复杂度:O(1)
     *      稳定性:稳定
     */
    public static void insertSort(int[] array) {
        for(int i = 1;i < array.length;i++) {
            int tmp = array[i];
            int j = i - 1;
            for(;j >= 0 ;j--) {
                if(array[j] > tmp) {
                    array[j + 1] = array[j];
                }else {
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }
    private static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    /**
     * 希尔排序
     *      1.对gap分组
     *      2.对分组分别直接插入排序
     *      3.最后一组必须是所有元素
     *      时间复杂度:O(N^1.25-N^1.5)
     *      空间复杂度:O(1)
     *      稳定性:不稳定
     */
    public static void shellSort(int[] array) {
        int gap = array.length;
        while(gap > 0) {
            gap /= 2;
            shell(array,gap);
        }
    }
    /**
     * 根据组数排序
     */
    public static void shell(int[] array,int gap) {
        for(int i = gap;i < array.length;i++) {
            int j = i - gap;
            int tmp = array[i];
            for(;j >= 0;j -= gap) {
                if(tmp < array[j]) {
                    array[j + gap] = array[j];
                }else {
                    break;
                }
            }
            array[j + gap] = tmp;
        }
    }
    /**
     * 直接选择排序1
     *      1.定义i j 如果array[j] < array[i],记录到minIndex,结束,交换
     *      2.i++,j = i + 1,继续判断
     *      时间复杂度:O(N^2)
     *      空间复杂度:O(1)
     *      稳定性:不稳定
     */
    public static void selectSort1(int[] array) {
        for(int i = 0;i < array.length;i++) {
            int j = i + 1;
            int minIndex = i;
            for(;j < array.length;j++) {
                if(array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            swap(array,i,minIndex);
        }
    }
    /**
     * 直接选择排序2
     *      1.定义left right放在左右 minIndex maxIndex记录最大/小下标,j遍历
     *      2.j结束交换,left right 改变
     *      注:如果maxIndex需要与left进行交换,则要记录下来minIndex交换后的下标,因为先交换小的,最小值下标就改变了
     *
     */
    public static void selectSort2(int[] array) {
        int left = 0;
        int right = array.length - 1;
        while(left < right) {
            int minIndex = left;
            int maxIndex = right;
            int j = left + 1;
            while(j <= right) {
                if(array[j] < array[minIndex]) {
                    minIndex = j;
                }
                if(array[j] > array[maxIndex]) {
                    maxIndex = j;
                }
                j++;
            }
            swap(array,left,minIndex);
            if(maxIndex == left) {
                maxIndex = minIndex;
            }
            swap(array,right,maxIndex);
            left++;
            right--;
        }
    }
    /**
     * 堆排序
     *      1.创建大根堆
     *      2.交换
     *      3.向下调整
     *      时间复杂度:O(Nlog2(为底)N)
     *      空间复杂度:O(1)
     *      稳定性:不稳定
     */
    public static void heapSort(int[] array) {
        createBigHeap(array);
        int end = array.length - 1;
        while(end > 0) {
            swap(array,0,end);
            siftDown(array,0,end);
            end--;
        }
    }
    /**
     * 创建大根堆
     */
    private static void createBigHeap(int[] array) {
        int parent = (array.length - 1 - 1) / 2;
        for(int i = parent;i >= 0;i--) {
            siftDown(array,i,array.length);
        }
    }
    /**
     * 向下调整
     */
    private static void siftDown(int[] array,int parent,int len) {
        int child = 2 * parent + 1;
        while(child < len) {
            if(child + 1 < len
                    && array[child] < array[child + 1]) {
                child++;
            }
            if(array[child] > array[parent]) {
                swap(array,child,parent);
                parent = child;
                child = 2 * parent + 1;
            }else {
                break;
            }
        }
    }
    /**
     * 冒泡排序
     *      1.创建i,j,j不断比较,如果大于后面值则交换,结束确定一个最大值,放在末尾
     *      2.i++,j进行第二趟比较,只需要比较前array.length - i - 1个即可每次确定一个
     *      3.i只要遍历array.length - 1趟
     *      时间复杂度:O(N^2)
     *      空间复杂度:O(1)
     *      稳定性:不稳定
     */
    public static void bubbleSort(int[] array) {
        for(int i = 0;i < array.length - 1;i++) {
            boolean flag = false;
            for(int j = 0;j < array.length - i - 1;j++) {
                if(array[j] > array[j + 1]) {
                    swap(array,j,j + 1);
                    flag = true;
                }
            }
            if(!flag) {
                break;
            }
        }
    }
}
